Optimization of data access typically entails an effort to move data and instructions among the various types of memory in order to best match the capabilities of the devices requiring the data. A typical computer system might be viewed as having three types of memory, namely high speed memory, random access memory (RAM), and mass memory. The high speed memory may consist of a small number of data registers or a larger number of registers forming a scratch pad memory. The random access memory typically consists of large arrays of solid state memory cells implemented as large scale integrated circuits. Mass memories may include semirandom access memories such as magnetic disks or sequential memories such as magnetic tape. These three types of memories, as listed above, may be considered to form a hierarchy, with the capacity increasing and the speed and cost decreasing as one goes down the list.
The remaining portions of this application will be concerned with the manner in which information is communicated between the random access memory (which will sometimes be referred to as "physical memory," "real memory," or simply "memory") and disk space
In order for a central processing unit to read or write an item of data, such item of data must reside in physical memory. Thus, if the size of a program exceeds the capacity of the RAM, provision must be made to swap portions of the program between the RAM and the disk. In order to relieve the programmer of this responsibility, an organizational technique known as "virtual memory" is used to increase the apparent size of the RAM. This illusion of a larger RAM is implemented by modifications that permit the operating system to replace unused blocks of words in the RAM with relevant blocks of words from the disk as the user addresses data that is not in physical memory.
Every virtual memory computer system has to provide some mechanism to translate a "virtual address" into a "physical address" that can be used to access memory. This is usually done by dividing the virtual addressing space into chunks and providing a translation or mapping system between an address designating a particular chunk in the virtual address space and the address of the corresponding chunk in physical memory. Where such chunks are of fixed size, they are typically referred to as "pages" which will be the term used in the remainder of this application.
For each page that can be addressed in the virtual space, there must exist a page descriptor which describes the state of that page in reality. The page may or may not reside in physical memory at any instant. If the page is in memory, the descriptor will indicate that fact and will indicate the location of the page in physical memory. If the page is not in physical memory, but is on disk, the descriptor will indicate that fact and will contain enough information for the system to access the page. The collection of all the page descriptors for a virtually addressable space is called a page map, and since each of the descriptors is an entry in this map, the page descriptors are referred to as the page map entries (PMEs).
The simplest page mapping system would be a linear array of PMEs stored in physical memory with the page number being used to index into the array. This mechanism is suitable for computers with only one virtual space, and a small one at that. However, if the virtual space becomes large, the page map itself becomes large, and consumes a large amount of physical memory. Moreover, in modern computer systems, protection of users (processes) is often provided by giving each process its own virtual space which may include one or more virtual subspaces.
These considerations have made it necessary to invent mechanisms whereby the individual page maps for the different processes need not all reside in physical memory at the same time. Thus, some systems allow the page map for each process to be swapped in when that process runs and swapped out again when it is not executing. However, this involves considerable overhead when switching between processes, and therefore the mechanism is not widely used in systems where processes are given large subspaces (which have large page maps).
A better and more widely used scheme requires that only parts of the page map be in physical memory at all times. The most common method, one used by the Digital Equipment Corporation (DEC) architecture, essentially places the process page map itself in a virtual space (in the case of VAX this is the operating system's virtual space). The page map for the system space has to be resident in memory, so that as the number of processes grows and the size of each of their spaces grows, the total size of user program page maps gets large. This makes the system virtual space large in turn makes the page map for the system large, thereby using up a large amount of physical memory. For example, VAX claims that a user can virtually address up to 2 Gigabytes (4M 512-byte pages). Such a page map would require 16 Megabytes, (32K pages) of system virtual space which requires 128 Kilobytes of physical memory to store the page system map. Thus, each process having 2 Gigabytes of virtual address space would use 128 Kilobytes of physical memory which would be unavailable for other uses.
A general problem with any virtual addressing system is to make sure that a process does not accidentally access a page that is outside that process' space. This requires a bounds check to verify that the address is within the permissible range. The VAX system described above handles the problem by requiring all processes to have the same maximum size space. The fixed size is a configuration parameter that is defined at the time the operating system is initialized. However, this size must be kept small to conserve real memory space.
Another feature of the above virtual addressing system is that the translation from virtual address of a byte to physical address of a byte always requires two accesses to memory, the first to find the location of the page map in physical memory and the second to find the location of the byte from the appropriate page map entry.